//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 
//
// 上图为 8 皇后问题的一种解法。 
//
// 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 
//
// 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 示例: 
//
// 输入: 4
//输出: [
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
//解释: 4 皇后问题存在两个不同的解法。
// 
//
// 
//
// 提示： 
//
// 
// 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步
//，可进可退。（引用自 百度百科 - 皇后 ） 
// 
// Related Topics 回溯算法 
// 👍 516 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：N皇后
public class P51NQueens {

    /**
     *
     * 思路： 回溯算法，一开始 核心的回溯用了两层的循环，发现有问题，后来看了一下网上的只用了一层，
     *
     * 执行用时： 6 ms , 在所有 Java 提交中击败了 40.16% 的用户 内存消耗： 39.8 MB , 在所有 Java 提交中击败了 79.87% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<List<String>> list = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            int[][] datas = new int[n][n];
            dfs(datas, 0, n);
            return list;
        }

        private void dfs(int[][] datas, int j, int n) {
            // j 大于n，代表循环结束，而且前面的都是没有冲突的，所以保存结果
            if (j >= n) {
                // 存起来
                List<String> tempList = new ArrayList<>();
                for (int a = 0; a < n; a++) {
                    StringBuilder sb = new StringBuilder("");
                    for (int b = 0; b < n; b++) {
                        if (datas[a][b] == 0) {
                            sb.append(".");
                        } else {
                            sb.append("Q");
                        }
                    }
                    tempList.add(sb.toString());
                }
                list.add(tempList);
                return;
            }

            for (int s = 0; s < n; s++) {
                // 检查是否不能放在此处
                if (checkRepeat(datas, j, s)) {
                    continue;
                }
                datas[j][s] = 1;
                dfs(datas, j + 1, n);
                // 不管成功与否，都得回溯
                datas[j][s] = 0;
            }
        }

        // 检查datas[j][k] 之前是否重复
        private boolean checkRepeat(int[][] datas, int j, int k) {
            int tempJ = j;
            int tempK = k;
            // 左斜
            while (j > 0 && k > 0) {
                if (datas[j - 1][k - 1] == 1) {
                    return true;
                }

                j--;
                k--;
            }
            j = tempJ;
            k = tempK;

            // 右斜
            while (j > 0 && k < datas.length - 1) {
                if (datas[j - 1][k + 1] == 1) {
                    return true;
                }
                j--;
                k++;
            }
            j = tempJ;
            k = tempK;

            // 横
            while (k > 0) {
                if (datas[tempJ][k - 1] == 1) {
                    return true;
                }
                k--;
            }
            // 纵
            while (j > 0) {
                if (datas[j - 1][tempK] == 1) {
                    return true;
                }
                j--;
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P51NQueens().new Solution();
        System.out.println(solution.solveNQueens(4));
        // TO TEST
    }

}